The present invention relates generally to media processors, and in particular, is directed to methods and systems for performing the faster two-dimensional inverse discrete cosine transforms (IDCT) in media processors.
A "media processor" is a type of computer which capable of processing video and audio signals. The market demand for fast media processors has increased with the demand for popular entertainment and consumer electronic goods. Typically, multimedia applications handle video and audio signs in real time and are often slow to execute. Media processors, therefore, are often specially designed for a particular application. Conventional media processors, for example, may have such features as a partitioned Single Instruction, Multiple Data (SIMD) architecture, custom instruction set, and wide registers to efficiently perform signal processing of image data. Another technique for improving media processors is to specially design the media processor to perform frequently required, time-intensive operations more efficiently.
Discrete cosine transforms (DCT) and inverse discrete cosine transform (IDCT) are widely used operations in the signal processing of image data. Both are used, for example, in the international standards for moving picture video compression put forth by the Motion Picture Experts Group (MPEG). DCT has certain properties that produce simplified and efficient coding models. When applied to a matrix of pixel data, the DCT is a method of decomposing a block of data into a weighted sum of spatial frequencies, or DCT coefficients. Conversely, the IDCT is used to transform a matrix of DCT coefficients back to pixel data.
FIG. 1 is a basic flow diagram showing the encoding and decoding processes of a prior art digital video (DV) codec. DV codecs are one example of a device using a DCT-based data compression method. In the blocking stage, the image frame is divided into N by N blocks of pixel information including, for example, brightness and color data for each pixel (stage 100). A common block size is eight pixels horizontally by eight pixels vertically. The pixel blocks are then "shuffled" so that several blocks from different portions of the image are grouped together (stage 110). Shuffling enhances the uniformity of image quality.
Different fields are recorded at different time incidents. For each block of pixel data, a motion detector looks for the difference between two fields of a frame (stage 115). The motion information is sent to the next processing stage (stage 120). In stage 120, pixel information is transformed using a DCT. An 8--8 DCT, for example, takes eight inputs and returns eight outputs in both vertical and horizontal directions. The resulting DCT coefficients are then weighted by multiplying each block of DCT coefficients by weighting constants (stage 125).
The weighted DCT coefficients are quantized in the next stage (stage 140). Quantization rounds off each DCT coefficient within a certain range of values to be the same number (stage 140). Quantizing tends to set the higher frequency components of the frequency matrix to zero, resulting in much less data to be stored. Since the human eye is most sensitive to lower frequencies, however, very little perceptible image quality is lost by this stage.
Quantization stage 140 includes converting the two-dimensional matrix of quantized coefficients to a one-dimensional linear stream of data by reading the matrix values in a zigzag pattern and dividing the one-dimensional linear stream of quantized coefficients into segments, where each segment consists of a string of zero coefficients followed by a non-zero quantized coefficient. Variable length coding (VLC) then is performed by transforming each segment, consisting of the number of zero coefficients and the amplitude of the non-zero coefficient in the segment, into a variable length codeword (stage 145). Finally, a framing process packs every 30 blocks of variable-length coded quantized coefficients into five fixed-length synchronization blocks (stage 150).
The lower portion of FIG. 1 shows a basic flow diagram of a prior art DV codec decoding process. Decoding is essentially the reverse of the encoding process described above. The digital stream is first deframed (stage 155). Variable length decoding (VLD) then unpacks the data so that it may be restored to the individual coefficients (stage 160).
After inverse quantizing the coefficients (stage 165), inverse weighting (stage 170) and an inverse discrete cosine transform (IDCT) (stage 175) are applied to the result. The inverse weights are the multiplicative inverses of the weights that were applied in the encoding process. The output of the inverse weighting function is then processed by the IDCT. The IDCT operation may be described mathematically using the following formula: ##EQU1##
where F.sub.N.times.N is an input matrix of DCT coefficients of size N by N, .function..sub.N.times.N is a output matrix of pixel information of size N by N, and c(u) and c(v) are matrices of constants as defined below. ##EQU2##
The result is then deshuffled (stage 180) and deblocked (stage 185) to form the full image frame.
Because the DCT and IDCT are widely used, much attention has been devoted to developing fast algorithms for implementing them. Furthermore, there exist many different, but mathematically equivalent, hardware and software implementations for computing the DCT and IDCT. For example, the IDCT equation above can also be written matrix notation as: EQU [.function..sub.N.times.N ]=[A.sub.N.times.N ].sup.T [F.sub.N.times.N ][A.sub.N.times.N ] (Equation 1)
where [A.sub.N.times.N ] is a N.times.N constant matrix. By applying simple rules of matrix multiplication, two mathematically equivalent matrix notation equations may be derived from Equation 1 as shown below. EQU [.function..sub.N.times.N ]=[A.sub.N.times.N ].sup.T ([A.sub.N.times.N ].sup.T [F.sub.N.times.N ].sup.T).sup.T (Equation 2) EQU [.function..sub.N.times.N ]=M([A.sub.N.times.N ].sup.T.times.[A.sub.N.times.N ].sup.T L([F.sub.N.times.N ].sup.T)) (Equation 3)
where L is an operation that converts an N.times.N matrix to a vector according to the equation L([X.sub.22 ])=[x.sub.00 x.sub.01 x.sub.10 x.sub.11 ], M is an operation that converts a vector into a matrix according to the equation [X.sub.22 ]=M([x.sub.00 x.sub.01 x.sub.10 x.sub.11 ]), and the symbol .times. indicates a tensor product. The tensor product of [X.sub.22 ].times.[Y.sub.22 ] is defined as, ##EQU3##
Equation 2 demonstrates that a two-dimensional IDCT may be computed by multiplying the input data matrix (F) by the constant matrix (A), transposing the result, and then multiplying the transposed matrix by the constant matrix (A). Algorithms that compute two-dimensional IDCTs in this manner are called "type I" algorithms. Type I algorithms are easy to implement on a parallel machine, that is, a computer formed of a plurality of processors operating simultaneously in parallel. For example, when using N parallel processors to perform a matrix multiplication on N.times.N matrices, N column multiplies can be simultaneously performed. Additionally, a parallel machine can be designed so as to contain special hardware or software instructions for performing fast matrix transposition.
One disadvantage of type I algorithms is that more multiplications are needed. The computation sequence of type I algorithms involves two matrix multiplies separated by a matrix transposition which, if N=4, for example, requires 64 additions and 48 multiplications for a total number of 112 instructions. It is well known by those skilled in the art that multiplications are very time-consuming for processors to perform and that system performance is often optimized by reducing the number of multiplications performed.
Equation 3 above demonstrates that the result of a two-dimensional IDCT can also be obtained by converting the transpose of the input matrix into a one-dimensional vector using the L function. Next, the tensor product [A.sub.N.times.N ].times.[A.sub.N.times.N ] of constant matrix [A.sub.N.times.N ] is obtained. Tensor product [A.sub.N.times.N ].times.[A.sub.N.times.N ] is then multiplied by the one-dimensional vector, L([F.sub.N.times.N ]). The result is converted back into an N.times.N matrix using the M function. Assuming again that N=4, the total number of instructions used by this computational sequence is 92 instructions (68 additions and 24 multiplications). Algorithms that perform two-dimensional IDCTs using this computational sequence are called "type II" algorithms. In type II algorithms, the two constant matrices are grouped together and performed as one operation. The advantage of type II algorithms is that they typically require fewer instructions (92 versus 112) and, in particular, fewer costly multiplications (24 versus 48). Type II algorithms, however, are very difficult to implement efficiently on a parallel machine. Type II algorithms tend to reorder the data very frequently and reordering data on a parallel machine is very time-intensive.
There exist numerous type I and type II algorithms for implementing IDCTs, however, all suffer from disadvantages that make them inefficient for use in a media processor. As explained above, media processors built using type I algorithms achieve some efficiencies from parallel processing but require too many instructions and, in particular, multiplications. Media processors built using type II algorithms require fewer instructions but cannot be further improved using parallel processing.
The present invention improves the efficiency of implementing an IDCT algorithm by providing methods and apparatus that minimize the number of required instructions. The present invention also provides methods and apparatus for decreasing the number of multiplications without reordering the data thereby allowing efficient implementation on a parallel machine.